Equal Sum Subarrays

Statement#

For a given array nums, determine if the array can be divided into two subarrays such that the sum of both the subarrays is equal.

For example, we have an array $[1, 2, 3]$ :

The total length of this array can be denoted as $n$ that is $3$ .
An array can only be divided into two equal subarrays if the total sum of the array is even. In this case, the total sum of array elements is $1 + 2 + 3 = 6$ , so two equal sum subarrays can be obtained here, as $[1, 2]$ and $[3]$ , both having an equal sum of $3$ .
In this case, TRUE will be returned as the array can be divided into two equal sum subarrays.
In case, the sum of array elements is odd or the array can not be divided into two equal sum subarrays, FALSE will be returned.

Constraints:

$1 \leq$ nums.length $\leq 200$
$1 \leq$ nums[i] $\leq 100$

Examples#

Naive approach#

We can solve this problem with the following two steps:

First, we calculate the sum of the array. If the sum of the array is odd, there can’t be two subarrays with an equal sum. Therefore, we return FALSE.
If the sum is even, we calculate Target Sum $=$ Array Sum $/2$ and find a subarray of the array with a sum equal to Target Sum. The subarray can be found by either including the current element or not including it. To include the current element, we need to subtract it from the Target Sum.

The first step can be calculated easily, and the second can be solved using recursion. In the recursive approach, we calculate the result repeatedly by decreasing the problem set and evaluating the solution at every stage. For example, consider an array [1, 2, 3, 2, 6, 2], that can be partitioned into [1, 2, 3, 2] and [6, 2], with the sum equal to 8.

Let’s implement the algorithm as discussed above:

def can_partition_array(nums):
    nums_len = len(nums)
    # base case
    if nums_len == 1:
        return False
    # calculate sum of array
    array_sum = sum(nums)
    # if array_sum is odd, it cannot be partitioned into equal sum subarrays
    if array_sum % 2 != 0:
        return False
    # calculating the target subarray sum
    target_sum = array_sum // 2
    return is_subarray_sum(nums, nums_len - 1, target_sum)
def is_subarray_sum(nums, nums_len, target_sum):
    if target_sum == 0:  # subarray formed with required half-sum
        return True
    if nums_len == 0 or target_sum < 0:
        return False
    # here we will perform two operations:
    # 1. include the current element therefore 'target_sum'
    #    will be updated as 'target_sum - current element'
    # or
    # 2. exclude current element therefore no need to update 'target_sum'
    result = (is_subarray_sum
             (nums, nums_len - 1, target_sum - nums[nums_len - 1]) 
                or is_subarray_sum(nums, nums_len - 1, target_sum))  
    return result

Enter to Rename, Shift+Enter to Preview

Equal Sum Subarrays using recursion

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array.

As the recursive approach shows, the sum 6 + 2 = 8 is computed twice, which takes extra time. We can avoid the repeated work done in the naive approach by storing the result calculated at each step.

We can use a dictionary named Memo that will store two things; the index of the element and the target sum. Using memoization and recursion to go further for any element in the array, we can:

Choose that element, in which case, the Target Sum will be updated as Target Sum $=$ Target Sum $-$ Nums [i].
If we ignore the $i^{th}$ element and move forward, Target Sum will remain the same.
If Target Sum $==0$ , then return TRUE.
If Target Sum $< 0$ , then return FALSE.

Let’s implement the algorithm as discussed above:

def can_partition_array(nums):
    nums_len = len(nums)
    # base case
    if nums_len == 1:
        return False
    # calculate sum of array
    array_sum = sum(nums)
    # if array_sum is odd, it cannot be partitioned into equal sum subarrays
    if array_sum % 2 != 0:
        return False
    # calculating the target subarray sum
    target_sum = array_sum // 2
    # Creating a memo to store two things:
    # (i) The index of array elements
    # (ii) The target sum
    memo = {}
    def is_subarray_sum(nums, index, target_sum):
        nums_len = len(nums)
        if target_sum == 0:  # Subarray formed with required half-sum
            return True
        if target_sum < 0 or index == nums_len:
            return False
        # here we will perform two operations:
        # 1. include the current element therefore target_sum
        #    will be updated as target_sum - current element

Enter to Rename, Shift+Enter to Preview

Equal Sum Subarrays using memoization

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. The problem is divided into subproblems, which are dependent on each other. We create a 2-D table of dimensions $(n + 1) \times (s + 1)$ , where $n$ is the size of the array and $s$ is the Target Sum calculated as Target Sum = Array Sum $/2$ , to store the result of subproblems. If we encounter the same sub-problem later, we can return the stored result from the table with a $O(1)$ lookup instead of recalculating that subproblem.

We will use the previously computed subproblem’s results in further calculations to fill the table indices by:

Place FALSE $(0)$ in the first row of the table and TRUE $(1)$ in the first column of the table.
Let’s assume that the $dp[i][j]$ means whether the Target Sum $j$ can be achieved from the first $i$ elements. If we can pick a series of numbers from $0$ to $i$ whose sum is $j$ , then $dp[i][j]$ is TRUE. Otherwise, it is FALSE.

The above step can be computed by using the following:
```
dp[i][j] = dp[i - 1][j - nums[i - 1]] or dp[i - 1][j]
```
Return the value of the last index of the table, which denotes whether the array can be partitioned.
- If we get $1$ (TRUE), the array can be partitioned.
- If we get $0$ (FALSE), the array can not be partitioned.

The value for $dp[1][1]$ can be calculated with the help of $dp[0][0]$ and $dp[1][0]$ , which are computed earlier. We don’t need to compute them again, which is the advantage of dynamic programming.

Let’s look at the following illustration to get a better understanding of the solution:

def can_partition_array(nums):
    array_sum = sum(nums)
    # if 'array_sum' is an odd number, we can't have 
    # two subarrays with equal sum
    if array_sum % 2 != 0:
        return False
    else:
    # We are trying to find a subarray of given numbers 
    # that has a total sum of 's/2'.
        target_sum = int(array_sum / 2)
    nums_len = len(nums)
    
    # Making a 2-D table.
    dp = [[0 for x in range(target_sum + 1)] for y in range(nums_len + 1)]
    
    # Intializng the first row with False and first column with True.
    for i in range(nums_len + 1):
        for j in range(target_sum + 1):
            if i == 0 and j == 0:
                dp[i][j] = True
            elif j == 0:
                dp[i][j] = True
            elif i == 0:
                dp[i][j] = False
    
    # Process all subarrays for all sums
    for i in range(1, nums_len + 1):

Enter to Rename, Shift+Enter to Preview

Equal Sum Subarrays using tabulation

No.	nums	Result
1	[1, 2, 3]	TRUE
2	[4, 2, 7]	FALSE
3	[2, 1, 5, 3, 1]	TRUE

Statement#

Examples#

Try it yourself#

Solution#

Naive approach#

Time complexity#

Space complexity#

Optimized solution using dynamic programming#

Top-down solution#

Time complexity#

Space complexity#

Bottom-up solution#

Time complexity#

Space complexity#